package com.wwz.leetcode;


import java.util.TreeMap;

/**
 * 求指定面积岛屿
 */
public class LeetCode200 {
    public static void main(String[] args) {
        String[][] grid = {
                {"1", "1", "0", "1", "1"},
                {"1", "1", "0", "1", "1"},
                {"0", "0", "0", "0", "0"},
                {"0", "0", "1", "0", "0"}
        };
        int s = 4;
        System.out.println(sumIslands(grid,s));


    }

    public static int sumIslands(String[][] grid,int s) {
        int sum = 0;
        int count = 0;
        TreeMap treeMap = new TreeMap();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == "1") {
                    TreeMap dfs = dfs(grid, i, j, sum, treeMap);
                    int res = Integer.valueOf(treeMap.get(dfs.lastKey()).toString());
                    if(res==s) {
                        count++;
                        treeMap.clear();
                    }
                }
            }
        }
        return count;
    }

    private static TreeMap dfs(String[][] grid, int i, int j,int sum,TreeMap treeMap) {

        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == "0") {
            return treeMap;
        }

        grid[i][j] = "0";
        sum++;
        dfs(grid, i + 1, j,sum,treeMap);//向下
        dfs(grid, i, j + 1,sum,treeMap);//向右
        dfs(grid, i - 1, j,sum,treeMap);//向上
        dfs(grid, i, j - 1,sum,treeMap);//向左
        treeMap.put(sum,sum);
        return treeMap;
    }
}
